1. Field
Embodiments of the invention relate to the field of networking; and more specifically, to computing a constraint based path.
2. Background
Constraint based path computation processes paths based on one or more constraints. For example, a network administrator may use constraint based path computation to select a path from a source to a destination based on one or more constraints. Generally, there are two types of constraints; Boolean constraints (e.g., cost of a link, available bandwidth of the link, link color, etc.) and additive constraints (e.g., number of hops limit). A Boolean constraint is a link type constraint (e.g., one hop type constraint) that requires a specific value for that link to be satisfied. Thus, evaluating whether a link satisfies a Boolean constraint depends only on that link. For example, for a link to satisfy an available bandwidth Boolean constraint (e.g., links must have an available bandwidth of 50), that link must meet or exceed the available bandwidth constraint. Thus, evaluating a Boolean constraint results in a value of True (link satisfies the constraint) or False (link does not satisfy the constraint). In contrast, an additive constraint is a path type constraint that is calculated on the basis of all the links in the path (e.g., multiple hops from the source to the destination). Thus, evaluating whether a path satisfies an additive constraint depends upon each link in the path (e.g., link characteristics of each link of the path are added and compared against the additive constraint). For example, for a path to satisfy a hop limit additive constraint (e.g., 3 hops or less), the number of hops (e.g., each link of the path) is added and compared against the hop limit additive constraint.
The characteristics of the links (e.g., cost, bandwidth, color, etc.) are propagated throughout the network using link-state routing protocols (e.g., Open Shortest Path First (OSPF) (described in Request For Comments (RFC) 2328, “OSPF Version 2”, April 1998), Intermediate System to Intermediate System (IS-IS) (described in International Standard ISO/IEC 10589:2002E, Nov. 15, 2002)). Typically these characteristics are stored in a traffic engineering database on each network element in the network. Thus, the traffic engineering database stores a representation of the topology of the network. A network element receives a service request for a path to a destination (thus the network element is the source) with one or more constraints (e.g., a network administrator, using a command line interface (CLI), requests a path to a destination given one or more constraints). The network element computes the requested path based on the constraints and the information in the traffic engineering database.
Several algorithms have been developed for computing constraint based paths. For example, several Constrained Shortest Path First (CSPF) algorithms have been developed. While no standard algorithm exists, a CSPF algorithm typically disregards those links from the network topology that do not meet the constraints and then performs a Shortest Path First (SPF) algorithm (e.g., a Dijkstra algorithm) on the remaining links. For example, all links that do not meet a given bandwidth constraint are disregarded and a SPF algorithm is performed on the remaining links to determine a path. It should be understood, however, that determining whether links meet the constraints is computationally expensive.